package oct2013;

import java.util.ArrayList;

public class SpiralMatrix {
	ArrayList<Integer> res;
	int[][] matrix;

	public ArrayList<Integer> spiralOrder(int[][] matrix) {
		res = new ArrayList<Integer>();
		this.matrix = matrix;
		int n = matrix.length;
		if (n == 0)
			return res;
		int m = matrix[0].length;
		dfs(0, 0, n, m);
		return res;
	}

	void dfs(int u, int l, int d, int r) {
		if (u > d || l > r)
			return;
		if (u == d) {
			for (int i = l; i <= r; ++i) {
				res.add(matrix[u][i]);
			}
			return;
		}
		if (l == r) {
			for (int i = u; i <= d; ++i) {
				res.add(matrix[i][l]);
			}
			return;
		}
		for (int i = l; i < r; ++i) {
			res.add(matrix[u][i]);
		}
		for (int i = u; i < d; ++i) {
			res.add(matrix[i][r]);
		}
		for (int i = r; i > l; --i) {
			res.add(matrix[d][i]);
		}
		for (int i = d; i > u; --i) {
			res.add(matrix[i][l]);
		}
		dfs(u + 1, l + 1, d - 1, r - 1);
	}
}
